package com.xyhuo.leetcode.january;

/**
 * 乘积最大子数组
 * https://leetcode.cn/problems/maximum-product-subarray/
 *
 * @time 2024/1/22
 */
public class MaxProduct {

    public int maxProduct(int[] nums) {
        int[][] dp = new int[2][nums.length];
        dp[0][0] = nums[0];
        dp[1][0] = nums[0];
        int ans = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int max = Math.max(dp[0][i - 1] * nums[i], dp[1][i - 1] * nums[i]);
            max = Math.max(max, nums[i]);

            int min = Math.min(dp[0][i - 1] * nums[i], dp[1][i - 1] * nums[i]);
            min = Math.min(min, nums[i]);

            dp[0][i] = max;
            dp[1][i] = min;
            if (max > ans) {
                ans = max;
            }
        }
        return ans;
    }
}
